//给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。 
//
// 你可以在 s 上按任意顺序多次执行下面两个操作之一： 
//
// 
// 累加：将 a 加到 s 中所有下标为奇数的元素上（下标从 0 开始）。数字一旦超过 9 就会变成 0，如此循环往复。例如，s = "3456" 且 a =
// 5，则执行此操作后 s 变成 "3951"。 
// 轮转：将 s 向右轮转 b 位。例如，s = "3456" 且 b = 1，则执行此操作后 s 变成 "6345"。 
// 
//
// 请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。 
//
// 如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符出现在字母表中的时
//间早于 b 中的对应字符。例如，"0158” 字典序比 "0190" 小，因为不同的第一个位置是在第三个字符，显然 '5' 出现在 '9' 之前。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "5525", a = 9, b = 2
//输出："2050"
//解释：执行操作如下：
//初态："5525"
//轮转："2555"
//累加："2454"
//累加："2353"
//轮转："5323"
//累加："5222"
//累加："5121"
//轮转："2151"
//累加："2050"​​​​​
//无法获得字典序小于 "2050" 的字符串。
// 
//
// 示例 2： 
//
// 
//输入：s = "74", a = 5, b = 1
//输出："24"
//解释：执行操作如下：
//初态："74"
//轮转："47"
//累加："42"
//轮转："24"​​​​​
//无法获得字典序小于 "24" 的字符串。
// 
//
// 示例 3： 
//
// 
//输入：s = "0011", a = 4, b = 2
//输出："0011"
//解释：无法获得字典序小于 "0011" 的字符串。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= s.length <= 100 
// s.length 是偶数 
// s 仅由数字 0 到 9 组成 
// 1 <= a <= 9 
// 1 <= b <= s.length - 1 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 字符串 枚举 👍 120 👎 0


package LeetCode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-10-19 00:07:10
 * @description 1625.执行操作后字典序最小的字符串
 */
public class LexicographicallySmallestStringAfterApplyingOperations{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LexicographicallySmallestStringAfterApplyingOperations fun=new LexicographicallySmallestStringAfterApplyingOperations();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 完全随机吧，确实不知道要按照什么顺序执行下一步会使得结果最小
	Set<String> visited = new HashSet<>();
	String ans;
    public String findLexSmallestString1(String s, int a, int b) {
		int[] array = s.chars().map(c -> c - '0').toArray();
		ans=s;
		visited.add(s);
		dfs(array,a,b);
		return ans;
    }
	public void dfs(int [] ar ,int a,int b){
		String current = stringify(ar);

		// 更新答案
		if (current.compareTo(ans) < 0) {
			ans = current;
		}

		// 操作1：对奇数位置加a
		int[] copy1 = ar.clone();
		funa(copy1, a);
		String str1 = stringify(copy1);
		if (!visited.contains(str1)) {
			visited.add(str1);
			dfs(copy1, a, b);
		}

		// 操作2：轮转b位
		int[] copy2 = ar.clone();
		funb(copy2, b);
		String str2 = stringify(copy2);
		if (!visited.contains(str2)) {
			visited.add(str2);
			dfs(copy2, a, b);
		}
	}

	private String stringify(int[] ar) {
		if (ar == null) {
			return "";
		}
		if (ar.length == 0) {
			return "";
		}

		StringBuilder sb = new StringBuilder();
		for (int num : ar) {
			sb.append(num);
		}
		return sb.toString();
	}

	public void funa(int[] array,int a){
		for (int i = 1; i < array.length; i+=2) {
			array[i]=(array[i]+a)%10;
		}
	}
	public void funb(int [] array,int b){
		int n = array.length;
		int[] temp = new int[n];
		for (int i = 0; i < n; i++) {
			temp[(i + b) % n] = array[i];
		}
		System.arraycopy(temp, 0, array, 0, n);
	}
	/*
题目有两种操作：

累加，将 s 的奇数位元素加上 a，超过 9 则回到 0 继续加。
轮转，将 s 向右轮转 b 位。
以上操作可以进行无限次，问可以得到的字典序最小的字符串。
注意到条件中 s 的长度是偶数，因此如果 b 是偶数，那么无论轮转多少次，我们都只能给 s 中奇数位的元素做累加操作。
但如果 b 是奇数的话，我们可以给 s 中奇数位和偶数位的元素都做加法，并且可以做不同的次数。
从以上可以看出，做累加操作的次数和做轮转操作的次数是互相独立的，做轮转的次数并不会影响到能否对偶数位进行累加。
因此我们可以先枚举做轮转的次数，然后再枚举做累加的次数，从而找到字典序最小的答案。
更具体的，我们按照如下步骤进行枚举：
枚举做轮转的次数，然后令 t 为 s 轮转后的字符串。由于轮转最终会产生循环，
且至多轮转 n 次（n 为 s 的长度），因此我们用一个数组 vis 来记录每个位置是否被轮转过。如果遇到之前轮转过的位置，则枚举结束。
对于每个 t，枚举对 t 的奇数位做累加操作的次数 j，再枚举对 t 的偶数位做累加操作的次数 k。
这里因为元素值范围是 [0,9]，因此我们做累加操作的次数上限是 9，再多势必会产生循环。特殊的，如果 b 是偶数，则 k 的上限是 0，否则是 9。
时间on2d2，d是枚举累加次数的上限
	* */
	public String findLexSmallestString(String s, int a, int b) {
		int n = s.length();
		// 最多轮转n次
		boolean[] vis = new boolean[n];
		String res = s;
		// 将 s 延长一倍，方便截取轮转后的字符串 t
		s = s + s;
		for (int i = 0; !vis[i]; i = (i + b) % n) {
			// 标记当前没有轮转过
			vis[i] = true;
			// 枚举对奇数位做累加操作的次数
			for (int j = 0; j < 10; j++) {
				// 枚举对偶数位做累加操作的次数，b是偶数则永远无法操作偶数位，否则和奇数位一样可以操作0-9次
				int kLimit = b % 2 == 0 ? 0 : 9;
				for (int k = 0; k <= kLimit; k++) {
					// 每次进行累加之前，重新截取 t，因为s已经延长过了，所以直接截取即可
					char[] t = s.substring(i, i + n).toCharArray();
					// 奇数位
					for (int p = 1; p < n; p += 2) {
						t[p] = (char) ('0' + (t[p] - '0' + j * a) % 10);
					}
					// 偶数位
					for (int p = 0; p < n; p += 2) {
						t[p] = (char) ('0' + (t[p] - '0' + k * a) % 10);
					}
					// 更新答案
					String tStr = new String(t);
					if (tStr.compareTo(res) < 0) {
						res = tStr;
					}
				}
			}
		}
		return res;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
